package com.lihepeng.leecode.solid_aim_offer.linkedlist;

import com.lihepeng.leecode.linkedList.ListNode;

/**
 * 链表的倒数第K 个节点
 * 描述
 * 输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
 * 如果该链表长度小于k，请返回一个长度为 0 的链表。
 *
 *
 * 数据范围：0 \leq n \leq 10^50≤n≤10
 * 5
 *  ，0 \leq a_i \leq 10^90≤a
 * i
 * ​
 *  ≤10
 * 9
 *  ，0 \leq k \leq 10^90≤k≤10
 * 9
 *
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 * 进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 *
 * 例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：
 */
public class Solution22 {
    // 使用快慢指针的方式来
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if (pHead ==null) {
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        // 让快节点 先走 k 步
        for (int i=0 ;i <k;i++) {
            if (fast ==null) {
                return null;
            }
            fast = fast.next;

        }

        while (fast!=null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

}
